package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2044 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int countMaxOrSubsets(int[] nums) {
            int allAnd = 0;
            for (int num : nums) {
                allAnd |= num;
            }
            return dfs(nums, 0, allAnd, 0);
        }

        public int dfs(int[] nums, int i, int allAnd, int curAnd) {
            if (i >= nums.length) return curAnd == allAnd ? 1 : 0;
            // 当前选 和 不选
            int choose = dfs(nums, i + 1, allAnd, curAnd | nums[i]);
            int notChoose = dfs(nums, i + 1, allAnd, curAnd);
            return choose + notChoose;
        }
    }

    public void run() {
        System.out.println(new Solution().countMaxOrSubsets(InputUtil.toIntegerArray("[3,1]")));
        System.out.println(new Solution().countMaxOrSubsets(InputUtil.toIntegerArray("[2,2,2]")));
        System.out.println(new Solution().countMaxOrSubsets(InputUtil.toIntegerArray("[3,2,1,5]")));
    }

    public static void main(String[] args) throws Exception {
        LC2044 an = new LC2044();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
